#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <utility>
//class Solution {
//public:
//    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
//        int prev = image[sr][sc];
//        if (prev == color)
//            return image;
//        queue<pair<int, int>> q;
//        q.push(make_pair(sr, sc));
//        while (!q.empty())
//        {
//            pair<int, int> tmp = q.front();
//            q.pop();
//            int r = tmp.first;
//            int l = tmp.second;
//            image[r][l] = color;
//            if (l - 1 >= 0 && image[r][l - 1] == prev)
//            {
//                q.push(make_pair(r, l - 1));
//            }
//            if (l + 1 < image[0].size() && image[r][l + 1] == prev)
//            {
//                q.push(make_pair(r, l + 1));
//            }
//            if (r + 1 < image.size() && image[r + 1][l] == prev)
//            {
//                q.push(make_pair(r + 1, l));
//            }
//            if (r - 1 >= 0 && image[r - 1][l] == prev)
//            {
//                q.push(make_pair(r - 1, l));
//            }
//        }
//        return image;
//    }
//};
//
//class Solution {
//public:
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int m, n;
//    int numIslands(vector<vector<char>>& grid) {
//        m = grid.size();
//        n = grid[0].size();
//        int ret = 0;
//        //queue<pair<int,int>> q;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == '1')
//                {
//                    //q.push(make_pair(i,j));
//                    change(grid, i, j);
//                    ret++;
//                }
//            }
//        }
//        return ret;
//    }
//    void change(vector<vector<char>>& grid, int i, int j)
//    {
//        queue<pair<int, int>> q;
//        grid[i][j] = '2';
//        q.push(make_pair(i, j));
//        while (!q.empty())
//        {
//            auto [l, r] = q.front();
//            q.pop();
//            //int x = tmp.first;
//            //int y = tmp.second;
//            grid[l][r] = '2';
//            for (int k = 0; k < 4; k++)
//            {
//                int x = l + dx[k];
//                int y = r + dy[k];
//                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1')
//                {
//                    grid[x][y] = '2';
//                    q.push(make_pair(x, y));
//                }
//            }
//        }
//    }
//};

class Solution {
public:
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m, n;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    ret = max(ret, bfs(grid, i, j));
                }
            }
        }
        return ret;
    }
    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        int ret = 1;
        queue<pair<int, int>> q;
        grid[i][j] = 2;
        q.push(make_pair(i, j));
        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k];
                int y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
                {
                    ret++;
                    grid[x][y] = 2;
                    q.push(make_pair(x, y));
                }
            }
        }
        return ret;
    }
};

class Solution {
public:
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    int m, n;
    void solve(vector<vector<char>>& board) {
        m = board.size();
        n = board[0].size();
        for (int i = 0; i < n; i++)
        {
            if (board[0][i] == 'O')
            {
                bfs(board, 0, i, 'Y');
            }
            if (board[m - 1][i] == 'O')
            {
                bfs(board, m - 1, i, 'Y');
            }
        }
        for (int i = 1; i < m - 1; i++)
        {
            if (board[i][0] == 'O')
            {
                bfs(board, i, 0, 'Y');
            }
            if (board[i][n - 1] == 'O')
            {
                bfs(board, i, n - 1, 'Y');
            }
        }
        for (int i = 1; i < m - 1; i++)
        {
            for (int j = 0; j < n - 1; j++)
            {
                if (board[i][j] == 'O')
                    bfs(board, i, j, 'X');
            }
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == 'Y')
                    board[i][j] = 'O';
            }
        }
    }
    void bfs(vector<vector<char>>& board, int i, int j, char ch)
    {
        queue<pair<int, int>> q;
        board[i][j] = ch;
        q.push(make_pair(i, j));
        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k];
                int y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
                {
                    board[x][y] = ch;
                    q.push(make_pair(x, y));
                }
            }
        }
    }
};
int main()
{
    vector<vector<int>> vv = { {1,1,1} ,{1,1,0},{1,0,1} };
    Solution().floodFill(vv, 1, 1,2);
    return 0;
}